package cn.dglydrpy.study.algorithm.od;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Yyy
 * @date 2024/11/7 22:39
 * @description
 * 简化多段线坐标表示，只保留关键点，根据输入的包含冗余数据的多段线坐标列表，输出最简化的结果。
 * 
 输入：
2 8 3 7 3 6 3 5 4 4 5 3 6 2 7 3 8 4 7 5
 输出：
2 8 3 7 3 5 6 2 8 4 7 5
 */
public class Od0023_DataZip {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String[] s = scanner.nextLine().split(" ");
            int[][] arr = new int[s.length/2][2];
            for(int i = 0;i<arr.length;i++){
                arr[i][0] = Integer.valueOf(s[2*i]);
                arr[i][1] = Integer.valueOf(s[2*i+1]);
            }
            
            String ans = myAnswer(arr);
            System.out.println(ans);

            String answer1 = answer1(arr);
            System.out.println(answer1);
        }
        
    }

    private static String myAnswer(int[][] arr) {
        StringBuilder ans = new StringBuilder();
        int[][] res = new int[arr.length][2];
        for(int i = 0;i<res.length;i++){
            res[i][0] = -1;
            res[i][1] = -1;
        }
        res[0][0] = arr[0][0];
        res[0][1] = arr[0][1];
   
        String preK = "";
        
        for(int i=1;i<arr.length;i++){

            String curK = k(arr[i][0],arr[i][1],arr[i-1][0],arr[i-1][1]);
            if(!curK.equals(preK)){
                res[i-1][0] = arr[i-1][0];
                res[i-1][1] = arr[i-1][1];
            }
            preK = curK;
            
            if(i == arr.length -1){
                res[i][0] = arr[i][0];
                res[i][1] = arr[i][1];
            }
            
        }
        
        for(int i=0;i<res.length;i++){
            if(res[i][0] != -1 && res[i][1] != -1){
                ans.append(res[i][0]).append(" ").append(res[i][1]).append(" ");
            }
        }
        
        return ans.toString().trim();
    }
    
    private static String k(int curX,int curY,int preX,int preY){
        int diffX = curX - preX;
        int diffY = curY - preY;
        
        if(diffY == 0 && diffX != 0){
            return "-";
        }
        if(diffX == 0 && diffY != 0){
            return "|";
        }
       
        return diffY/diffX + "";
    }

    private static final int DIRECT_1 = 1;
    private static final int DIRECT_2 = 2;
    private static final int DIRECT_3 = 3;
    private static final int DIRECT_4 = 4;
    private static final int DIRECT_5 = 5;
    private static final int DIRECT_6 = 6;

    public static String answer1(int[][] arr) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(new int[]{arr[i][0], arr[i][1]});
        }
        return handle(list);
    }

    private static String handle(List<int[]> list) {
        if (list.size() <= 1) {
            return "";
        }
        List<int[]> result = new ArrayList<>();
        result.add(list.get(0));
        int direct = direct(list.get(0), list.get(1));
        int[] before = list.get(1);
        for (int i = 2; i < list.size(); i++) {
            int[] curr = list.get(i);
            int direct_res = direct(before, curr);
            if (direct_res!= direct) {
                result.add(before);
                direct = direct_res;
            }
            before = curr;
        }
        result.add(list.get(list.size() - 1));
        StringBuilder output = new StringBuilder();
        for (int[] i : result) {
            output.append(i[0]).append(" ").append(i[1]).append(" ");
        }
        output.deleteCharAt(output.length() - 1);
        return output.toString();
    }

    private static int direct(int[] before,int[] after) {
        int row1 = before[0];
        int col1 = before[1];
        int row2 = after[0];
        int col2 = after[1];
        if (row1 == row2) {
            return DIRECT_1;
        } else if (col1 == col2) {
            return DIRECT_2;
        } else if (row1 + 1 == row2 && col1 + 1 == col2) {
            return DIRECT_3;
        } else if (row1 + 1 == row2 && col1 - 1 == col2) {
            return DIRECT_4;
        } else if (row1 - 1 == row2 && col1 - 1 == col2) {
            return DIRECT_5;
        } else if (row1 - 1 == row2 && col1 + 1 == col2) {
            return DIRECT_6;
        }
        return 0;
    }
 
}
